package bin_tree.heap;

import java.util.ArrayList;

/**
 * 基于数组实现的最大堆
 * 编号从0开始，假设当前节点为i，i>0
 * parent = (i - 1) / 2
 * 若有左右孩子，保证2i + 1或2i + 2 < data.length
 * left = 2i + 1;
 * right = 2i + 2;
 */
public class MaxHeap {
    //具体存储元素的动态数组
    private ArrayList<Integer> data;
    public MaxHeap(){
        data = new ArrayList<>();
    }
    public MaxHeap(int capicity){
        data = new ArrayList<>(capicity);
    }
    public void add(int val){
        data.add(val);
        //调整堆的结构
        siftUp(data.size() - 1);
    }
    public int extractMax(){
        if (isEmpty()){
            System.out.println("heap is empty!");
            return -1;
        }
        int max = data.get(0);
        //将最后一个元素顶到堆顶
        int lastVal = data.get(data.size() - 1);
        data.set(0,lastVal);
        //移除堆顶元素
        data.remove(data.size() - 1);
        siftDown(0);
        return max;
    }
    private void siftDown(int i) {
        while (left(i) < data.size()){
            int j = left(i);
            //取出左右孩子最大值
            if(right(i) < data.size()){
                int leftVal = data.get(left(i));
                int rightVal = data.get(right(i));
                if(leftVal < rightVal){
                    j = j + 1;
                }
            }
            //j一定是左右孩子最大值
            //data[i] 和 data[j]
            if(data.get(i) >= data.get(j)){
                //当前节点已经大于左右孩子，下沉结束
                break;
            }else {
                swap(i,j);
                i = j;
            }
        }
    }

    /**
     * 元素上浮操作
     * @param i
     */
    private void siftUp(int i) {
        while (i > 0 && data.get(i) > data.get(parent(i))){
            //swap
            swap(i,parent(i));
            //继续向上判断
            siftUp(parent(i));
        }
    }
    //交换当前数组中
    private void swap(int i, int parent) {
        int tmp = data.get(i);
        int parventVal = data.get(parent);
        data.set(i,parventVal);
        data.set(parent,tmp);
    }
    //heapify,堆化
    public MaxHeap(int[] arr){
        data = new ArrayList<>(arr.length);
        for (int i : arr){
            data.add(i);
        }
        for (int i = parent(data.size() - 1); i >= 0 ; i--) {
            siftDown(i);
        }
    }
    public boolean isEmpty(){
        return data.size() == 0;
    }
    //三个私有方法
    private int parent(int k){
        return (k - 1) / 2;
    }
    private int left(int k){
        return 2 * k + 1;
    }
    private int right(int k){
        return 2 * k + 2;
    }
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < data.size();i++){
            sb.append(data.get(i));
            if(i != data.size() - 1){
                sb.append(",");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}

















